class Solution:
    def permute(self, nums):
        n = len(nums)
        result = []
        path = []
        used = [False] * n  # 标记 nums[i] 是否已被使用

        def backtrack():
            if len(path) == n:
                result.append(path[:]) # 这里加上[:]表示浅拷贝。如果不加的话，最后 path 被 pop() 清空了，而 result 里所有元素都指向这个空列表
                return
            
            for i in range(n):
                if not used[i]:          # O(1) 判断是否可用
                    used[i] = True       # 【做选择】
                    path.append(nums[i])
                    
                    backtrack()          # 【递归】
                    
                    path.pop()           # 【撤销选择】
                    used[i] = False      # 回溯时释放标记

        backtrack()
        return result

if __name__ == '__main__':
    nums = [1, 2, 3]
    solution = Solution()
    result = solution.permute(nums)
    print(result)

# 回溯 = 递归 + 选择 + 撤销选择

# 执行流程：
# 开始 path=[]
# ├─ 选1 → path=[1]
# │   ├─ 选2 → path=[1,2]
# │   │   └─ 选3 → path=[1,2,3] → 加入 result
# │   └─ 选3 → path=[1,3]
# │       └─ 选2 → path=[1,3,2] → 加入 result
# ├─ 选2 → path=[2]
# │   ├─ 选1 → path=[2,1]
# │   │   └─ 选3 → [2,1,3]
# │   └─ 选3 → path=[2,3]
# │       └─ 选1 → [2,3,1]
# └─ 选3 → path=[3]
#     ├─ 选1 → [3,1,2]
#     └─ 选2 → [3,2,1]